Suppose a person want to travel
from one city to another with are connected by several paths , these kind
of problems are called Shortest - Path problem , in these kind of
problems we are given a weighted graph G = (V,E) with a weight fuction
and weight of path is sum of weights of its costituent edges.
Dijkstra's Algorithm
Dijkstra's algorithm solves the single -source shortest-path
problem on a weighted ,directed graph G=(V,E) for the case in which
all the weights are non negetive.
Algorithm
1. Initialize-Single-Source(G,s)
2. S<--null
3. Q<--V[G]
4. while Q != null
5. do
u<--Extract-Min(Q)
6.
S<--S union {u}
7.
for each vertex V belonging to Adj[u]
8.
do Relax(U,V,W)
Working
of Algorithm
Line 1 performs
the usual initialisation of distance and parent values ,and Line
2 initialize the empty set S.Line 3 initialize the priority Queue Q to
contain all the vertices in V-S = V-null =V.Each time through the while
loop of lines 4-8 ,a vertex is extracted from Q = V-S and inserted into
set S.Vertex U therefore has the smallest path estimated of any vertex
in V-S.then the Line 7-8 relax each Edge (U,V) leaving u.The run time of
Algorithm is thus O(sq. V + E) = O(sq. V).
Execution of the Dijkstra's Algorithm
The shortest path estimates are shown within the vertices. and red edges indicate predeccesor values : if edge (u,v) is red ,then parent of v is u.green vertices are in the set S,and the blue vertices are in the Priority Queue Q = V-S.
(a) The situation just before the first iteration of the while loop of lines 4-8.The shaded vertex has minimum d value and is choosen as vertex u in line 5.
(b>-(f) The situation after each succesive iteration of the while loop.The green vertex in each part is choosen as vertex u in line 5 of the next iteration.
Run Animation
Keys to Home
Dijkstra's Graph Algorithm
This tutorial was written
by Abhishek Goyal,Marghoob Mohiyuddin,Pooja Nath and Ruchi Saran |
Please email comments to:
[email protected][email protected] |
© Abhishek
Goyal
, 1999